package treeNode

// iteration
/*
前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点
*/
func PreorderTraversalRecursive(root *TreeNode) *[]int {
	var result []int
	if root == nil {
		return &[]int{}
	}
	result = append(result, root.Value)
	result = append(result, *PreorderTraversalRecursive(root.LeftNode)...)
	result = append(result, *PreorderTraversalRecursive(root.RightNode)...)
	return &result
}

func PreorderTraversalIteration(root *TreeNode) *[]int {

	if root == nil {
		return &[]int{}
	}
	result := make([]int, 0)
	stack := make([]*TreeNode, 0)
	for root != nil || len(stack) != 0 {
		for root != nil {
			result = append(result, root.Value)
			stack = append(stack, root.RightNode)
			root = root.LeftNode
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
	}
	return &result
}

//中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
func InorderTraversal(root *TreeNode) *[]int {
	result := make([]int, 0)
	if root == nil {
		return &result
	}
	stack := make([]*TreeNode, 0)
	for root != nil || len(stack) != 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.LeftNode
		}
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		result = append(result, node.Value)
		root = node.RightNode
	}
	return &result

}

//后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点
func PostorderTraversal(root *TreeNode) *[]int {
	result := make([]int, 0)
	if root == nil {
		return &result
	}
	stack := make([]*TreeNode, 0)
	var lastVisit *TreeNode
	for root != nil || len(stack) != 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.LeftNode
		}
		// 这里先看看，先不弹出
        node:= stack[len(stack)-1]
        // 根节点必须在右节点弹出之后，再弹出
        if node.RightNode == nil || lastVisit == node.RightNode {
            stack = stack[:len(stack)-1] // pop
            result = append(result, node.Value)
            // 标记当前这个节点已经弹出过
            lastVisit = node
        } else {
            root = node.RightNode
        }
		
	}
	return &result
}